package com.LeeCode;

import java.util.HashMap;

/**
 * 和相同的二元子数组
 */

public class Code930 {
    public static void main(String[] args) {
        int[] nums = {1, 0, 1, 0, 1};
        int goal = 2;
        System.out.println(new Code930().numSubarraysWithSum1(nums, goal));
    }

    public int numSubarraysWithSum(int[] nums, int goal) {
        int ans = 0;
        int sum1 = 0, left1 = 0, sum2 = 0, left2 = 0;

        for (int right = 0; right < nums.length; right++) {
            sum1 += nums[right];
            sum2 += nums[right];

            while (left1 <= right & sum1 >= goal) {
                sum1 -= nums[left1++];
            }
            while (left2 <= right & sum2 >= goal + 1) {
                sum2 -= nums[left2++];
            }

            ans += left1 - left2;

        }
        return ans;
    }

    public int numSubarraysWithSum1(int[] nums, int goal) {
        int ans = 0, sum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int num : nums) {
            sum += num;
            int target = sum - goal;
            ans += map.getOrDefault(target, 0);
            map.merge(sum, 1, Integer::sum);
        }
        return ans;
    }
}
